#ifndef __CONTEXTFREE__

#define __CONTEXTFREE__

#include"namestorage.h"
#include<vector>
#include<map>
#include<string>
#include<iostream>

//dirty hack: int number represents an arbitrary CF symbol:
// positive one corresponds to non-terminal number,
// negative one to terminal's ASCII value

class CFGrammar {
	
	static NameStorage names;
	static NameStorage initNames();
	static std::string resolve(int);
	static std::string resolve(std::vector<int> const &);
	static std::string resolve(std::vector<int> const & vi,
			std::vector<int>::const_iterator vit);
	static std::set<std::vector<int> > mutateRule(std::vector<int> const &,
		std::multimap<unsigned, unsigned> const &);
	static std::vector<int> unresolve(std::string const &);
	static bool CNFRule(std::vector<int> const &); 
	static bool CNFChainRule(std::vector<int> const &);
	static std::pair<unsigned, std::vector<int> > getRuleFromStream(std::istream &);
	static std::string extractAlNum(std::string const &);
	static std::multimap<unsigned, unsigned> transClosure(std::multimap<unsigned, unsigned>);
	
	unsigned starting;	
	std::multimap<unsigned, std::vector<int> > rules;
	bool clean;
	bool chainCNF;
	bool CNF;
	
	public:
	
	CFGrammar();	
	CFGrammar(CFGrammar const &);
	~CFGrammar();
	
	void cleanup();
	CFGrammar cleanedup() const;
	void chainNormalize();
	CFGrammar chainNormalized() const;	
	void normalize();
	CFGrammar normalized() const;
	
	bool CYK(std::string const &) const;
	
	friend std::ostream & operator<<(std::ostream &, CFGrammar const &);
	friend std::istream & operator>>(std::istream &, CFGrammar &);
	 
};

#endif 
